package two.stack_queue;

import java.util.Stack;

/**
 * 接雨水
 * 时间复杂度：O(n)
 * 思路：前缀和（后缀和）||单调栈
 */
public class Trap {

    //方法一：前缀最大值（后缀最大值） O(n)
    //方法一的思路：纵向求和 一个柱子正上方最多能积多少水（取决于这个柱子前后最大柱子的二者最小值，与这根柱子的高度差）
    public int trap(int[] height) {
        int n = height.length;
        int[] pre = new int[n + 1]; //柱子前缀最大值
        int[] suf = new int[n + 2]; //柱子后缀最大值
        for(int i = 1; i <= n; i++) pre[i] = Math.max(pre[i - 1], height[i - 1]);
        for(int i = n; i >= 1; i--) suf[i] = Math.max(suf[i + 1], height[i - 1]);
        int ans = 0;
        for(int i = 1; i <= n; i++){
            ans += Math.max(0, Math.min(pre[i - 1], suf[i + 1]) - height[i - 1]);
        }
        return ans;
    }
    //方法二：单调栈（维护一个单调递减的序列，当突然递增就要出栈计算）O(n)
    //方法二的思路：横向求和
    public int trap2(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int ans = 0; //结果
        //步骤一：for循环每一个元素
        for(int i = 0; i < height.length; i++){
            //步骤二：while（不满足栈的单调性时，计算，出栈《==》可以积水时，计算，出栈）
            while(!stack.empty() && height[stack.peek()] < height[i]){
                int top = stack.pop();
                if(stack.isEmpty()){
                    break;
                }
                int distance = i - stack.peek() - 1;
                int h2 = Math.min(height[i], height[stack.peek()]) - height[top];
                ans += distance * h2;
            }
            //步骤三：入栈
            stack.push(i);
        }
        return ans;
    }
}
